The invention relates to a word group priority device for assigning priorities to word groups in a store on the basis of the least-recently used criterion, where in the case of a read operation or write operation in a word group or in the case of the replacement of a word group having the lowest priority, this word group is assigned the highest priority and the priority of all word groups having a priority higher than that of this word group is lowered by one step, the device comprising a code generator for generating for each operation in the store the relevant priority codes associated with the word groups. Word group priority devices of this kind are known and are notably used in storage systems consisting of a main store having a large storage capacity and a fast buffer store having a small storage capacity. In this context, a set of information, which may be a store word and/or a number of store words which together form a block, is generally referred to as "word group". The buffer store of the storage systems serves for storing the most relevant and the most frequently used word groups. It is thus achieved that the processors of a computer system including such a storage system can operate more efficiently. The speeds of the buffer store and the processors then have the same order of magnitude. Because the capacity of the buffer store is only limited, always a decision must be taken as regards which word group must be replaced by another word group in order to satisfy at any instant the condition that the buffer store must contain the most relevant and most frequently used word groups.
A suitable and already often used criterion for the decision as regards which word group must be replaced by another word group is the "least-recently used" criterion. This means that a word group in the buffer store which has least recently been used best qualifies for replacement. In other words, a word group of this kind has the lowest priority as regards further stay in the buffer store. The other word groups in the buffer store have an increasing priority, in dependence of their history. The word group which has most recently been used and/or which has been given new contents has the highest priority.
As will be obvious from the preamble of this description, the present invention relates to a word group priority device in which the "least-recently used" criterion is embodied. The known solutions for such priority devices are often complex combinatory logic networks which produce the desired codes wherefrom the necessary replacement and priority adaptation of the other word groups of the buffer store is derived. The delay time incurred in such a network before the assignment of new priorities has been completed is very important. If this delay time is too long, the advantage of such a buffer store arrangement diminishes. In order to mitigate this drawback, proposals have been made which resulted in simpler solutions for the priority device, but these proposals introduced the drawback that the "least recently used" criterion is no longer completely satisfied. This also implies a reduction of the efficiency of such a storage system comprising a buffer store.
The invention has for its object to eliminate these drawbacks and to provide a word group priority device which has a simple construction but which still fully satisfied the "least recently used" criterion. To this end, the word group priority device in accordance with the invention is characterized in that the generator comprises means for supplying priority codes (m bits), a first number of bits (k) of each priority code serving for the identification of the group having the lowest priority of all groups, the further (m - k) bits of each priority code serving for the coding of all priority combinations for the groups which do not have the lowest priority, K being smaller than m - k, and furthermore comprising a signal line on which it is signalled that a read operation or a write operation is performed in a word group or that a word group is replaced, and a register for storing a generated priority code (initial code) which serves, in conjunction with the signalling, as a selection code for a priority code to be newly generated, and a decoder which determines, on the basis of the first (k) bits of each newly generated priority code, which word group has the lowest priority. First of all, a simple code for determining the word group having the lowest priority (in view of the replacement of this group) has thus been realized. This code comprises a minimum number of bits (k &lt; m - k), so that it is ensured that the determination of the group having the lowest priority is effected in the quickest manner (after minimal decoding). Secondly, the means enabling the coding of all priority combinations for the groups which do not have the lowest priority are thus also limited, notably for systems involving three to six word groups; this not only results in a saving as regards space but offers notably the advantage that little time is lost during the renewed generating of these codes.
A preferred embodiment of the device in accordance with the invention is characterized that a read-only store (suitable for rewriting or not) is used as the core of the priority generator. A further preferred embodiment of the device in accordance with the invention is characterized in that the read-only store comprises primary and secondary selection means, a generated priority code providing a primary selection in the read-only store, the signalling of the read or write operation in a word group or the replacement of a word group in the store providing the secondary selection in the read-only store.
In computer configurations utilizing such storage systems comprising a main store and a buffer store, situations occur in which a word group of the buffer store is to be invalidated, for example, if a parity error is detected. If a plurality of processors are used in a computer system and each processor comprises its own buffer store, invalidations can also occur. If a given processor modifies a word group in the main store, the word group also being present in a buffer store of a different processor, this word group must be invalidated.
For the present invention it is important to establish what can be done with such an invalidation signalling, regardless the origin of such an invalidation. Thus far, according to this signalling only a special bit was added to the address of the relevant word group present in the address store associated with the buffer store. During the comparison of an address of a requested word group with the addresses, present in the address store, of the word groups present in the buffer store, it could be seen that a given word group was invalid and access to the relevant address in the main store itself had to be effected. The construction of the word group priority device in accordance with the invention also enables simple use of this invalidation signalling in a different manner. To this end, the word group priority device in accordance with the invention is characterized in that there is provided a signalling line on which it is signalled that a word group has been invalidated, the generator comprising further means for generating priority codes in accordance with the defined code, the invalidated word group being assigned the lowest priority and the priority of all groups having a priority lower than that of this group being raised by one step, a priority code (initial code) stored in the register serving, in conjunction with the signalling of the invalidation, as a selection code for the priority code to be generated by the generator. It is thus achieved that a word group which is invalid anyway, first qualifies for replacement by another word group, because this word group has been assigned the lowest priority. Moreover, in the device in accordance with the invention it is also possible for the signalling of the invalidation of a word group to provide the secondary selection in the read-only memory.
Finally, in view of the high cost of hardware e.g., (decoders), it is more advantageous to produce the priority codes from storage, using a minimum number of bits, to specify the codes for the group having the lowest priority.